package org.algorithm.熊猫.数组.二月;

import java.util.Arrays;

/**
 * @author 熊猫
 * @version 1.0
 * @date 2022/03/0 9:07 PM    星期一的作业
 * @description: <p>
 * 数组中三数相加最接近target
 * 输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 * </p>
 * <p>
 * uri: https://leetcode-cn.com/problems/3sum-closest/solution/hua-jie-suan-fa-16-zui-jie-jin-de-san-shu-zhi-he-b/
 */
public class 最接近的三数之和 {

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1};
        System.out.println(threeSumClosest(nums, 4));
    }

    public static int threeSumClosest(int[] nums, int target) {
        if (nums.length <= 3) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            return sum;
        }
        Arrays.sort(nums);

        int base = 10000000;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int a = nums[i];
            int bI = i + 1, cI = n - 1;

            while (bI < cI) {
                int sum = nums[i] + nums[bI] + nums[cI];
                if (Math.abs(sum - target) < Math.abs(base - target)) {
                    base = sum;
                }
                if (sum > target) {
                    int cc = cI - 1;
                    //相同则往下跳过
                    while (bI < cc && nums[cc] == nums[cI]) {
                        --cc;
                    }
                    cI = cc;

                } else if (sum < target) {
                    int bb = bI + 1;
                    //相同则往下跳过
                    while (bb < cI && nums[bb] == nums[bI]) {
                        ++bb;
                    }
                    bI = bb;
                } else {
                    return sum;
                }
            }

        }
        return base;
    }
}
